The present invention relates to a multiprocessor caching system. In particular, the present invention relates to a method and apparatus for caching dynamically-changing data in a multiprocessor environment.
Multiprocessor computing systems typically use a caching server disposed between the processors and a common file server to improve system performance. For instance, to improve access by client terminals to HTML servers in a World Wide Web environment, an enterprise uses a web server for caching HMTL data requested by all of the enterprise""s client terminals. In addition, each client terminal is equipped with a dedicated software cache which caches the HTML data requested by the client terminal.
This approach increases system performance since a subsequent request by a client terminal for static HTML data previously requested from an HTML server can be satisfied locally by accessing either the terminal""s dedicated cache or the web server cache, without having to request the data again from the HTML server. However, the conventional caching server cannot offer improved system performance for client queries based on dynamically-changing data, since the caching server cannot determine if the data upon which a previous query was based has changed. Instead, the conventional web caching server accesses web search engines to satisfy client data queries based on dynamically changing data. Still, web search engines typically satisfy search queries by maintaining and periodically updating a database of web server content. Consequently, web search engines frequently return search results which consists of pointers to data which has long since expired.
Attempts have been made to improve the performance of multi-processor computing systems in respect of dynamically-changing data. For instance, Gannon (U.S. Pat. No. 5,265,232) discloses a multiple processor caching system which includes a storage controller, a cross-invalidate directory stored in the storage controller, and a number of processors in communication with the storage controller. Each processor has its own private L1 store-through cache and associated L1 cache directory. The system also includes a shared L2 cache and/or a main memory.
The cross-invalidate directory has entries each associated with a respective data unit of the L2 cache and main memory. Each cross-invalidate directory entry includes a processor identifier field identifying which processor owns the associated data, and indicates whether the ownership is exclusive or public. Exclusive ownership means that only one of the processors has ownership over the data unit (ie. the identified processor can write to the data unit). Public ownership means that all of the processors have ownership over the data unit (ie. all processors can read from but not write to the data unit).
If one of the processors requests a change in ownership over a data unit (eg. to overwrite the data unit), the request identifies the data unit to be changed, the requesting processor and the ownership type requested. The storage controller queries the directory for the processors which have ownership over the data unit, and transmits a request to the identified processors to terminate their respective ownerships over the data unit, both in the L1 and the L2 cache. Each processor which receives the request updates their respective L1 cache directory to indicate that the data unit is no longer available in their respective L1 cache, and then signals the storage controller that the processor has terminated its ownership over the data unit. Once all ownership over the data unit has terminated, the storage controller updates the cross-invalidate directory to reflect the new ownership of the data unit, and then modifies the data unit in the L2 cache and main memory as requested by the requesting processor. The other processors must then access the L2 cache or main memory to obtain a copy of the modified data unit (copying same into their respective L1 cache).
Mackenthun (U.S. Pat. No. 6,122,711) discloses a dual cluster multi-processing system which includes a pair of multi-processing clusters interconnected with a main memory and a system controller over a local area network. Each cluster includes a number of processors each having a dedicated store-through cache. Each cluster also includes a storage controller connected to the processors. The storage controller includes a second level cache, and a database of tags. The tags include copies of the data in the first level caches of the processors which are connected to the respective storage controller. The tags also include flags which identify the status of each cache clement (valid, modified), and the processor which xe2x80x9cownsxe2x80x9d the cache element. If a processor intends to write to its second level cache, the processor must be designated as the owner of the cache element. Only one processor can be designated as the owner of a cache element, although the owner can change.
If a processor (eg. of the first cluster) requests access to a data element, the first storage controller checks its tag database to determine if the element is cached in the second level cache and, if so, if the data in the cached element is valid. If the cached element is present and valid, the first storage controller retrieves the cached element for the processor from the second level cache.
However, if the cached element is not present, or is not valid, the second storage controller checks its tag database to determine if it has a valid cached copy of the data element. If the second storage controller does not have a cached copy of the data element, the data is retrieved from the main memory and stored in the second level cache of the first storage controller. The first storage controller then updates its tag database to indicate that the first storage controller is the owner of the cache element, and provides the processor with the cached element.
On the other hand, if the second storage controller does have a valid cached copy of the data element, the second storage controller transmits the cached element to the first storage controller, and then invalidates its own copy of the cached element by updating the appropriate flag in its tag database. The first storage controller then updates its tag database to indicate that the first storage controller is the owner of the cache element, and provides the processor with the cached element.
If the processor of the first cluster subsequently modifies the cached element, the first storage controller keeps a copy of the modified cached element in its second level cache, and then updates its tag database to indicate that the cached data is different from the data stored in the main memory. If an operator subsequently decides to remove one of the clusters from the system, the system controller retrieves from the first storage controller all second level cache elements which are owned by the first storage controller and whose corresponding tag indicates that the cached data is different from the data stored in the main memory. The system controller then stores the retrieved data in the main memory.
Although both Gannon and Mackenthun are able to offer some improvement in system performance in respect of dynamically-changing data, the performance improvement is limited by the need for a centralized storage controller which controls access by the processors to the shared data. In both solutions, a write request must be acted upon by the storage controller before access to the shared data is granted.
Further, both solutions are unable to provide any improvement in system performance for network clients making similar data queries based on the dynamically-changing data, since the caches can only mirror the contents of the main system memory. These limitations render both solutions inadequate for widely-distributed multi-processing environments, such as World Wide Web computing.
Accordingly, there remains a need for a computing solution which can enhance system performance in respect of dynamically-changing data in a widely-distributed multi-processing environment.
According to a first aspect of the present invention, there is provided a method of caching data, which involves the steps of:
receiving from one of a number of network clients a request for a data item;
creating a private cache uniquely associated with the network client;
initiating association of the private cache with a shared cache, the shared cache including the requested data item and being associated with a number of the network clients; and
updating the private cache with the requested data item.
According to a second aspect of the present invention, there is provided a caching server which includes:
receiving means for receiving from one of a number of network clients a request for a data item;
cache establishing means in communication with the receiving means for creating a private cache uniquely associated with the one network client;
cache associating means in communication with the cache establishing means for initiating association of the private cache with a shared cache, the shared cache including the requested data item and being associated with a number of the network clients; and
updating means for updating the private cache with the requested data item.
According to a third aspect of the present invention, there is provided a method of caching dynamically-variable data, which involves the steps of:
maintaining a store of dynamically-variable data and a shared cache, the shared cache being associated with a plurality of network clients and including a subset of the data store;
receiving from one of the network clients a data update to the shared cache, and storing the updated data in at least the shared cache;
receiving from one other of the network clients a request for an item of the variable data; and
initiating updating of a private cache associated with the one other network client, the private cache being uniquely associated with the one other network client and including a respective portion of the data subset, the data portion including the requested data item and cache data corresponding to the updated data.
According to a fourth aspect of the present invention, there is provided a caching server which includes:
a shared cache associated with a plurality of network clients;
data update means in communication with the shared cache for receiving from one of the network clients a data update to the shared cache, and storing the updated data in at least the shared cache;
receiving means for receiving from one other of the network clients a request for an item of the variable data; and
updating means for updating a private cache associated with the one other network client, the private cache being uniquely associated with the one other network client and including a respective portion of the data subset, the data portion including the requested data item and cache data corresponding to the updated data.
According to a fifth aspect of the present invention, there is provided a method of caching dynamically-variable data, which involves the steps of:
maintaining a store of dynamically-variable data, the data store including one of application data, and user session data;
dynamically establishing a first level cache and a second level cache in response to a request for the stored data, the caches caching data comprising a subset of the stored data; and
dynamically removing at least one of the caches after invalidation thereof.